package LK_DP;

public class DP_Day_2 {
    /* 爬楼梯
    * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
      每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
      * f(n)方法总数=f(n-1)+f(n-2)*/
    public int climbStairs(int n) {
        int f1=1;
        int f2=2;
        int sum=0;
        if (n <= 2){
            return n;
        }
        while (n > 2){
            sum=f1+f2;
            f1=f2;
            f2=sum;
            n--;
        }
        return sum;
    }
    /*使用最小花费爬楼梯
    * 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。
    * 一旦你支付此费用，即可选择向上爬一个或者两个台阶。
     你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
     请你计算并返回达到楼梯顶部的最低花费。
     * dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])*/
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
}
